package com.tencent;

import java.util.Arrays;

/**
 * @className: com.tencent.QuickSort
 * @description: 快速排序
 * @author: tong.li
 * @createTime: 2023/2/22 19:15
 * @copyright: Tongcheng-Elong Holdings Limited
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] arr = {6 ,4,8,1, 5};
        System.out.println("排序前:" + Arrays.toString(arr));
        sort(arr, 0, arr.length-1);
        System.out.println("排序后:" + Arrays.toString(arr));
        // int a = 3,b =8;
        // a = a ^ b;
        // b = a ^ b;
        // a = a ^ b;
        // System.out.println("a=" + a + "b=" + b);
        // swap(arr, 0, arr.length-1);
        // System.out.println("排序前:" + Arrays.toString(arr));
    }


    /**
     * 对整个数组进行排序
     * @param arr
     */
    // public static void sort(int[] arr) {
    //     // 合法性校验，都没元素或为null，那排个毛啊
    //     if (arr == null || arr.length == 0) {
    //         return;
    //     }
    //     sort(arr, 0, arr.length-1);
    // }

    /**
     * 分组排序
     * @param arr
     * @param low
     * @param high
     */
    public static void sort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int partIdx = part(arr, low, high);
        // 左子组排序，递归
        sort(arr, low, partIdx - 1);
        // 右子组排序，递归
        sort(arr, partIdx + 1, high);
    }


    /**
     * 分区交换归位
     * @param arr
     * @param low
     * @param high
     */
    public static int part(int[] arr, int low, int high) {
        // 定义基准位
        int base = arr[low], left = low, right = high + 1;
        while (true) {
            while (compare(base, arr[--right])) {
                if (low == right) {
                    break;
                }
            }
            while (!compare(base, arr[++left])) {
                if (left == high) {
                    break;
                }
            }
            if (left >= right) {
                break;
            }
            swap(arr, left, right);
        }
        // 基准归位
        swap(arr, low, right);
        return right;
    }



    /**
     * 交换元素
     * @param arr
     * @param start
     * @param end
     */
    public static void swap(int[] arr, int start, int end) {
        // 这里先用临时变量交换
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }


    /**
     * 比较两个数大小，用于后续排序判断，目前是按升序排
     * @param v1
     * @param v2
     * @return
     */
    public static boolean compare(int v1, int v2) {
        return v1 > v2;
    }
}
